

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>

#include "common/utils.hpp"

void traversal(std::vector<std::string> &ret, std::vector<int> &path, TreeNode* node) {
    path.push_back(node->val);
    // 到叶子节点 返回结果
    if (node->left == nullptr && node->right == nullptr) {
        std::string tmp;
        int len = path.size();
        for (int i = 0; i < len - 1; i++) {
            tmp += std::to_string(path[i]);
            tmp += "->";
        }
        tmp += std::to_string(path[len - 1]);
        ret.push_back(tmp);
        
        return;
    }

    // 继续遍历左子树
    if (node->left != nullptr) {
        traversal(ret, path, node->left);
        path.pop_back();
    }

    // 继续遍历右子树
    if (node->right != nullptr) {
        traversal(ret, path, node->right);
        path.pop_back();
    }
}

std::vector<std::string> binaryTreePaths(TreeNode* root) {
    std::vector<std::string> ret;
    std::vector<int> path;
    if (root == nullptr) return ret;

    traversal(ret, path, root);

    return ret;
}

extern TreeNode* commonRoot;

int main() {
    std::vector<std::string> ret = binaryTreePaths(commonRoot);
    std::cout << "res: " << "\n";
    for (int i = 0; i < ret.size(); i++) {
        std::cout << ret[i] << "\n";
    }
}